package org.hegang.algorithm.insertionsort;

/**
 * @ClassName InsertionSort
 * @Describe: 插入排序, 稳定排序
 * @Author: gang.he
 * @Email: SmileSkylife@outlook.com
 * @Date: Created in 22:10 2019/7/4
 * @Modified_By: TODO
 * @Version: V1.0
 */
public class InsertionSort {
    public static void insertionSort(int[] insertionSort) {
        if (insertionSort == null || insertionSort.length == 0) {
            return;
        }
        for (int i = 1; i < insertionSort.length; i++) {
            for (int j = i; j > 0; j--) {
                if (insertionSort[j] < insertionSort[j - 1]) {
                    int temp = insertionSort[j];
                    insertionSort[j] = insertionSort[j - 1];
                    insertionSort[j - 1] = temp;
                }
            }
        }
    }

    /**
     * 交换运算换成赋值运算，提升效率
     *
     * @param insertionSort
     */
    public static void optimizationInsertionSort(int[] insertionSort) {
        if (insertionSort == null || insertionSort.length == 0) {
            return;
        }
        for (int i = 1; i < insertionSort.length; i++) {
            int temp = insertionSort[i];
            int j;
            // 提前终止内层循环，提升效率
            for (j = i; j > 0 && temp < insertionSort[j - 1]; j--) {
                insertionSort[j] = insertionSort[j - 1];
            }
            insertionSort[j] = temp;
        }
    }
}
